#include <vector>
#include <iostream>

using namespace std;

// 时间复杂度: 平均O(n * k) 最坏O(n * k) 最好O(n * k)
// 空间复杂度: O(n + k)
// 稳定性: 稳定排序
class RadixSort {
private:
    static int getMaxDigit(int *array, int length) {
        if (length == 0) {
            return 0;
        }

        int max_value = array[0];
        for (int i = 0; i < length; ++i) {
            max_value = max(max_value, array[i]);
        }

        int digit = 0;
        while (max_value != 0) {
            digit++;
            max_value /= 10;
        }

        return digit;
    }

    static int getBucketIndex(int value, int base) {
        if (value < base / 10) {
            return 0;
        }

        value %= base;

        while (10 <= value) {
            value /= 10;
        }

        return value;
    }

public:
    static void radixSort(int *array, int length) {
        int max_digit = getMaxDigit(array, length);

        int base = 10;
        for (int i = 0; i < max_digit; ++i) {
            vector<int> bucket[10];

            for (int j = 0; j < length; ++j) {
                int value = array[j];
                int index = getBucketIndex(value, base);
                bucket[index].push_back(value);
            }

            int count = 0;
            for (vector<int> const &concrete_bucket : bucket) {
                for (int const &value : concrete_bucket) {
                    array[count++] = value;
                }
            }

            base *= 10;
        }
    }
};